package com.youth.day01;

/**
 * 基数排序
 * @author Jinx
 * @date 2021/6/14 1:08
 */
public class BaseSort {


    /**
     *  时间复杂度：O(n)
     *  <p></p>
     *  分析：
     *  外层轮数：10（以Integer为例，最大）  因为他是最大数除以10  所以循环次数是个常量10
     *  内层取出：n
     *  内层还原：10n（structCount是个常量10，structCount[j]可能为n，所以总体10n）
     *
     *  最终：10 * （n + 10n）  -> n  （但是常数项还是很大的）
     *  <p></p>
     *  用最底层的实现方法 HahMap啥的都不要用了
     */
    @SuppressWarnings("all")
    public static int[] sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr;
        }

        // 二维数组   第一层存0-9  第二层存具体的数（其实二维数组就相当于集合嵌套集合）
        int[][] struct = new int[10][arr.length];
        // 二维数组中第一层已存元素个数   用于确定角标   因为不能直接根据struct[i]确定其元素个数，只知道长度不像集合有个size()方法
        int[] structCount = new int[10];

        // 找到数组中最大的数 确定遍历轮数
        int max = 0;
        for (int j : arr) {
            max = Math.max(j, max);
        }

        // round:轮数对应的位数  为1时取个位  10时十位
        for (int i = 0, round = 1; i <= max/10; i++, round *= 10) {
            for (int j = 0; j < arr.length; j++) {
                int index = arr[j]/round % 10;
                struct[index][structCount[index]++] = arr[j];
            }

            // 把数据取出来开始下一轮（第一轮完事后个位有序  第二轮十位 。。。）
            int index = 0;
            for (int j = 0; j < structCount.length; j++) {
                if(structCount[j] > 0){
                    for (int k = 0; k < structCount[j]; k++) {
                        arr[index++] = struct[j][k];
                    }
                    structCount[j] = 0;
                }
            }
        }

        return arr;
    }
}
